#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

void Adjustup(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void HeapInit(Heap* php)
{
	assert(php);
	php->_a = NULL;
	php->_size = php->_capacity = 0;
}

void HeapDestory(Heap* php)
{
	assert(php);
	free(php->_a);
	php->_a = NULL;
}

void HeapPush(Heap* php, HPDataType x)
{
	assert(php);

	if (php->_capacity == php->_size)
	{
		int newcapacity = php->_capacity == 0 ? 4 : php->_capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->_a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");

			exit(1);
		}
		php->_a = tmp;
		php->_capacity = newcapacity;
	}

	php->_a[php->_size] = x;
	php->_size++;

	Adjustup(php->_a, php->_size - 1);
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child <n)
	{
		if ((child+1<n)&& (a[child+1] > a[child]))
			child++;
		if(a[child]>a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

void HeapPop(Heap* php)
{
	assert(php);
	assert(php->_size > 0);
	Swap(&php->_a[0], &php->_a[php->_size - 1]);
	php->_size--;
	
	AdjustDown(php->_a, php->_size, 0);
}

HPDataType HeapTop(Heap* php)
{
	assert(php);

	return php->_a[0];
}

int HeapSize(Heap* php)
{
	assert(php);
	return php->_size;
}

int HeapEmpty(Heap* php)
{
	return php->_size == 0;
}

void Heapsort(int* a, int n)
{
	for (int i = (n-1-1)/2; i >=0; i--)
	{
		AdjustDown(a, n,i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a,end,0 );
		end--;
	}
}